/*
 * @Author: 缄默
 * @Date: 2021-12-11 19:42:17
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-11 20:35:09
 */

//子数组异或和为0的最多划分

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int mostEOR(vector<int>& arr);

int main() {
    vector<int> arr({3, 2, 1, 9, 0, 7, 0, 2, 1, 3});
    cout << mostEOR(arr) << endl;
    return 0;

}

int mostEOR(vector<int>& arr) {
    if (arr.size() == 0) return 0;
    int eor = 0;
    //定义dp数组
    vector<int> dp(arr.size());

    //利用map来存储以i结尾的最短的异或为0的划分

    map<int, int> hashMap;
    hashMap[0] = -1;
    dp[0] = arr[0] == 0 ? 1 : 0;
    hashMap[arr[0]] = 0;
    for (int i = 1; i < arr.size(); i++) {
        //不断地累计异或
        eor ^= arr[i];
        //如果异或结果之前出现证明从之前出现到i之间的数的异或值为0
        if (hashMap.count(eor)) {
            int preEorIndex = hashMap[eor];
            //如果上次出现过 记录下组为dp[i]
            dp[i] = preEorIndex == -1 ? 1 : (dp[preEorIndex] + 1);
        }

        //和i不被划分进去的dp【i-1】作比较，记录dp[i]的值
        dp[i] = max(dp[i - 1], dp[i]);
        hashMap[eor] = i;
        
    }
    return dp[arr.size() - 1];
}
